UVa/11842 - Flatland/11842.3.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 #define DEBUG false
  29 #define dprintf DEBUG and printf
  30 #define dcout DEBUG and cout
  31
  32 inline int cmp(double x, double y = 0, double tol = 1e-9) {
  33     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  34 }
  35
  36 int Width, Height;
  37
  38 struct Vector {
  39     double x, y;
  40     Vector() {}
  41     Vector(double X, double Y) : x(X), y(Y) {}
  42     inline void normalize() {
  43         double length = sqrt(x * x + y * y);
  44         x /= length; y /= length;
  45     }
  46     bool operator < (const Vector &o) const {
  47         if (cmp(x, o.x) != 0) return cmp(x, o.x) < 0;
  48         return cmp(y, o.y) < 0;
  49     }
  50     bool operator == (const Vector &o) const {
  51         return (cmp(x, o.x) == 0 and
  52             cmp(y, o.y) == 0);
  53     }
  54 };
  55
  56 struct Person {
  57     double x, y;
  58     Vector d;
  59     string name;
  60
  61     Person(){}
  62     Person(double X, double Y, const Vector &D, string Name) : x(X), y(Y), d(D.x, D.y), name(Name) {}
  63
  64     bool operator < (const Person &o) { return name < o.name; }
  65
  66     double timeToFall() const;
  67
  68     friend ostream &operator<<(ostream &stream, const Person &p);
  69 };
  70
  71 double Person::timeToFall() const {
  72     double horizontal = cmp(this->d.x, 0) < 0 ? this->x / (-this->d.x) : (Width - this->x) / (this->d.x);
  73     double vertical   = cmp(this->d.y, 0) < 0 ? this->y / (-this->d.y) : (Height - this->y) / (this->d.y);
  74     return min(horizontal, vertical);
  75 }
  76
  77 ostream &operator<<(ostream &stream, const Person &p) {
  78     stream << p.name << " is at (" << p.x << ", " << p.y << ") moving in direction <" << p.d.x << ", " << p.d.y << "> (Might fall in " << p.timeToFall() << " seconds)";
  79     return stream;
  80 }
  81
  82 struct Death {
  83     string name;
  84     double time;
  85     Death(){}
  86     Death(const string &Name, double Time) : name(Name), time(Time) {}
  87     bool operator < (const Death &o) const {
  88         if (cmp(time, o.time) != 0) return cmp(time, o.time) < 0;
  89         return name < o.name;
  90     }
  91 };
  92
  93 struct Collision {
  94     double time;
  95     Vector point; // point of collision, if any
  96     vector<int> people; // the guy who fell or the two fellows that collided (contains indexes)
  97
  98     Collision(){}
  99     Collision(double Time) : time(Time) {}
 100     Collision(double Time, double x, double y, int personA, int personB) : time(Time), point(x, y) {
 101         people = vector<int>(2); people[0] = personA; people[1] = personB;
 102     }
 103
 104     bool operator < (const Collision &o) const {
 105         if (cmp(time, o.time) != 0) return cmp(time, o.time) < 0;
 106         return point < o.point;
 107     }
 108 };
 109
 110 double dot(const Vector &a, const Vector &b) {
 111     return a.x * b.x + a.y * b.y;
 112 }
 113
 114 bool outsideWorld(double x, double y) {
 115     if (cmp(x, 0) < 0) return true;
 116     if (cmp(x, Width) > 0) return true;
 117     if (cmp(y, 0) < 0) return true;
 118     if (cmp(y, Height) > 0) return true;
 119     return false;
 120 }
 121
 122 // Returns the time where person A and B would collide, or -1 if they won't.
 123 Collision collisionBetween(const Person &a, const int indexOfA, const Person &b, const int indexOfB) {
 124     if (Vector(a.x, a.y) == Vector(b.x, b.y)) {
 125         return Collision(-1.0); // They are on the same point, won't collide.
 126     }
 127
 128     double x0 = a.x, x1 = a.x + a.d.x;
 129     double y0 = a.y, y1 = a.y + a.d.y;
 130
 131     double x2 = b.x, x3 = b.x + b.d.x;
 132     double y2 = b.y, y3 = b.y + b.d.y;
 133
 134     double t0 = (y3-y2)*(x0-x2)-(x3-x2)*(y0-y2);
 135     double t1 = (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
 136     double det = (y1-y0)*(x3-x2)-(y3-y2)*(x1-x0);
 137
 138     if (cmp(det, 0) == 0){
 139       //parallel
 140         if (cmp(t0, 0) == 0 || cmp(t1, 0) == 0) {
 141           // they lie on same line. But they might not collide (if they travel in the same direction)
 142             if (cmp(dot(a.d, b.d), 1) == 0) { // They travel in the same direction
 143                 return Collision(-1.0);
 144             }
 145             Vector pointOfCollision(x0 + (x2 - x0) / 2,
 146                 y0 + (y2 - y0) / 2);
 147
 148             double dist = hypot(x2 - x0, y2 - y0) / 2;
 149             if (cmp(x0 + dist * a.d.x, pointOfCollision.x) != 0 or cmp(y0 + dist * a.d.y, pointOfCollision.y) != 0 or
 150             cmp(x2 + dist * b.d.x, pointOfCollision.x) != 0 or cmp(y2 + dist * b.d.y, pointOfCollision.y) != 0) {
 151                 // they travel in opposite directions, but after traveling half the distance they haven't collided, so they'll never collide
 152                 return Collision(-1.0);
 153             }
 154             return Collision(dist, pointOfCollision.x, pointOfCollision.y, indexOfA, indexOfB); // they'll collide in half their distance because they travel in opposite directions
 155         }
 156         //just parallel, no intersection
 157         return Collision(-1.0);
 158     }
 159
 160     t0 /= det;
 161     t1 /= det;
 162
 163     if (cmp(t0, t1) == 0 and cmp(0.0, t0) <= 0 and cmp(0.0, t1) <= 0){
 164         double x = x0 + t0*(x1-x0);
 165         double y = y0 + t0*(y1-y0);
 166         if (outsideWorld(x, y)) return Collision(-1.0);
 167         return Collision(t0, x, y, indexOfA, indexOfB);
 168     }
 169     return Collision(-1.0);
 170 }
 171
 172 bool collidesWithSomeone(const vector< Person > &people, int i) {
 173     for (int j = 0; j < people.size(); ++j) {
 174         if (i == j) continue;
 175         Collision c = collisionBetween(people[i], i, people[j], j);
 176         dprintf("Colission between %s and %s:\n    Time = %lf, x=%lf, y=%lf\n", people[i].name.c_str(), people[j].name.c_str(), c.time, c.point.x, c.point.y);
 177         assert(cmp(c.time, 0) != 0); // if they collided, assert it wasn't at time 0
 178         if (cmp(c.time, 0) > 0) { // Bang!
 179             return true;
 180         }
 181     }
 182     return false;
 183 }
 184
 185
 186 // If there's someone who doesn't collide, it's added to the deaths vector and removed from the people vector.
 187 vector< Person > killOrBouncePeople(vector< Person > people, vector < Death > &deaths, double &elapsedTime) {
 188     for (int i = 0; i < people.size(); ++i) {
 189         if (!collidesWithSomeone(people, i)) {
 190             dcout << people[i].name << " doesn't collide with anyone. Killing!" << endl;
 191             deaths.push_back( Death(people[i].name, elapsedTime + people[i].timeToFall()) );
 192             vector < Person > ans;
 193             for (int j = 0; j < people.size(); ++j) {
 194                 if (i != j) ans.push_back(people[j]);
 195             }
 196             return ans;
 197         }
 198     }
 199
 200     // Everybody collides here
 201     for (int i = 0; i < people.size(); ++i) assert(collidesWithSomeone(people, i));
 202
 203     // Now process collisions, by time.
 204     vector< Collision > collisions;
 205     for (int i = 0; i < people.size(); ++i) {
 206         for (int j = i + 1; j < people.size(); ++j) {
 207             Collision c = collisionBetween(people[i], i, people[j], j);
 208             if (cmp(c.time, 0) > 0) {
 209                 collisions.push_back( c );
 210             }
 211         }
 212     }
 213     assert(collisions.size() > 0);
 214     sort(collisions.begin(), collisions.end());
 215
 216     int i = 0, n = collisions.size();
 217     set<int> peopleWhoDiedInCollisions;
 218
 219     while (i < n and cmp(collisions[0].time, collisions[i].time) == 0) {
 220         int j = i;
 221         while (j < n and cmp(collisions[i].time, collisions[j].time) == 0 and collisions[i].point == collisions[j].point) {
 222             j++;
 223         }
 224         // collisions[i..j) have the same point and time)
 225         dprintf("Processing slice [i=%d, j=%d) of collisions:\n", i, j);
 226         for (int k = i; k < j; ++k) {
 227             dprintf("    Collision[k=%d]: time = %lf, x = %lf, y = %lf, people.size() = %d\n", k, collisions[k].time, collisions[k].point.x, collisions[k].point.y, (int)collisions[k].people.size());
 228         }
 229
 230         if (j - i == 1) { // two people
 231             // just swap their names
 232             int personA = collisions[i].people[0], personB = collisions[i].people[1];
 233             dprintf("Two people collided: %s and %s\n", people[personA].name.c_str(), people[personB].name.c_str());
 234             swap(people[personA].name, people[personB].name);
 235         } else { // more than two people
 236             for (int k = i; k < j; ++k) {
 237                 peopleWhoDiedInCollisions.insert( collisions[k].people.begin(), collisions[k].people.end()  );
 238             }
 239         }
 240
 241         i = j;
 242     }
 243
 244     vector< Person > newPeople;
 245     for (i = 0; i < people.size(); ++i) {
 246         if (peopleWhoDiedInCollisions.count(i) > 0) {
 247             deaths.push_back( Death(people[i].name, elapsedTime + collisions[0].time) );
 248         } else {
 249             Person p = people[i];
 250             p.x += collisions[0].time * p.d.x;
 251             p.y += collisions[0].time * p.d.y;
 252             newPeople.push_back( p );
 253         }
 254     }
 255     elapsedTime += collisions[0].time;
 256     dprintf("Elapsed time: %lf\n", elapsedTime);
 257     return newPeople;
 258 }
 259
 260 int main(){
 261     int Cases; cin >> Cases;
 262     while (Cases--) {
 263         dprintf("\n\n\n\nBegin case:\n");
 264         int n; cin >> n;
 265         cin >> Width >> Height;
 266
 267         vector<Person> people;
 268         for (int i = 0; i < n; ++i) {
 269             Person p;
 270             cin >> p.x >> p.y >> p.d.x >> p.d.y >> p.name;
 271             assert(cmp(floor(p.x), p.x) == 0 and cmp(floor(p.y), p.y) == 0); // people lie on integer coordinates
 272             p.d.x -= p.x; p.d.y -= p.y; p.d.normalize();
 273             people.push_back(p);
 274             dcout << p << endl;
 275         }
 276
 277         vector< Death > deaths;
 278         double elapsedTime = 0;
 279         while (people.size() > 0) {
 280             people = killOrBouncePeople(people, deaths, elapsedTime);
 281             dprintf("Remaining people:\n");
 282             for (int i = 0; i < people.size(); ++i) {
 283                 dcout << "       " << people[i] << endl;
 284             }
 285         }
 286         sort(deaths.begin(), deaths.end());
 287         for (int i = 0; i < deaths.size(); ++i) {
 288             dprintf("%s died at %lf\n", deaths[i].name.c_str(), deaths[i].time);
 289         }
 290         printf("%s\n", deaths.back().name.c_str());
 291     }
 292     return 0;
 293 }